package 动态规划;

/**
 * @Author: biubiu0002
 * @Date: 2021-09-25 11:23
 **/
public class LCS最长公共子序列 {
    public static void main(String[] args) {

    }

    //设dp[i][j]表示[x0..xi] 和 [y0..yj]的 公共字符
    public int LCS(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        char[] s1 = word1.toCharArray();
        char[] s2 = word2.toCharArray();

        if (word1.equals(word2)) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 0;
                }
                if (i > 0 && j > 0) {
                    char c1 = s1[i-1];
                    char c2 = s2[j-1];
                    if (c1 != c2) {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    } else if (c1 == c2) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                }
            }
        }
        return dp[m][n];

    }
}
